from collections import Counter
from math import comb


class Solution:

    def numTilePossibilities(self, tiles: str) -> int:
        cnt = Counter(tiles)
        n = len(tiles)

        def f(i):
            if i == n:
                return 1
            ans = 1
            for k, v in cnt.items():
                if v > 0:
                    cnt[k] -= 1
                    ans += f(i + 1)
                    cnt[k] += 1
            return ans

        return f(0) - 1


class Solution():

    def numTilePossibilities(self, tiles: str) -> int:
        cnts = Counter(tiles).values()
        n, m = len(tiles), len(cnts)
        f = [[0] * (n + 1) for _ in range(m + 1)]
        f[0][0] = 1
        for i, c in enumerate(cnts, 1):
            for j in range(n + 1):
                for k in range(min(j, c) + 1):
                    f[i][j] += f[i - 1][j - k] * comb(j, k)
        return sum(f[m][1:])


class Solution:

    def numTilePossibilities(self, tiles: str) -> int:
        f = [1] + [0] * len(tiles)
        n = 0
        for cnt in Counter(tiles).values():  # 枚举第 i 种字母
            n += cnt  # 常数优化：相比从 len(tiles) 开始要更快
            for j in range(n, 0, -1):  # 枚举序列长度 j
                # 枚举第 i 种字母选了 k 个，注意 k=0 时的方案数已经在 f[j] 中了
                for k in range(1, min(j, cnt) + 1):
                    f[j] += f[j - k] * comb(j, k)  # comb 也可以预处理，见其它语言的实现
        return sum(f[1:])


f = [[i for i in range(5)] for _ in range(5)]

for row in f:
    print(row)

print(f[4][1:])

f = [1] + [0] * 5

print(f)
